// //
// // Created by Jody on 2025/2/16.
// //
//
// #include <iostream>
// #include <vector>
//
// // 迭代版本
// int binarySearch(const std::vector<int>& arr, int target) {
//     int left = 0;
//     int right = arr.size() - 1;
//
//     while (left <= right) {  // 注意循环条件
//         // 防止整数溢出的写法
//         int mid = left + (right - left) / 2;
//
//         if (arr[mid] == target) {
//             return mid;
//         } else if (arr[mid] < target) {
//             left = mid + 1;  // 调整左边界
//         } else {
//             right = mid - 1; // 调整右边界
//         }
//     }
//     return -1;  // 未找到
// }
//
// // 递归版本
// int binarySearchRecursive(const std::vector<int>& arr, int target, int left, int right) {
//     if (left > right) return -1;
//
//     int mid = left + (right - left) / 2;
//     if (arr[mid] == target) {
//         return mid;
//     } else if (arr[mid] < target) {
//         return binarySearchRecursive(arr, target, mid + 1, right);
//     } else {
//         return binarySearchRecursive(arr, target, left, mid - 1);
//     }
// }
//
// int main() {
//     std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
//
//     // 测试迭代版本
//     std::cout << "find 9 index: " << binarySearch(arr, 9) << std::endl;     // 输出4
//     std::cout << "find 6 index: " << binarySearch(arr, 6) << std::endl;     // 输出-1
//
//     // 测试递归版本
//     std::cout << "\nrecursion find" << std::endl;
//     std::cout << "find 13 index: "
//               << binarySearchRecursive(arr, 13, 0, arr.size()-1) << std::endl; // 输出6
//     std::cout << "find 0 index: "
//               << binarySearchRecursive(arr, 0, 0, arr.size()-1) << std::endl;  // 输出-1
//
//     return 0;
// }